<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>排序算法之桶排序</title>
  </head>
  <body>
    <script type="text/javascript">
      // 默认情况下，我们会使用 5 个桶。桶排序在所有元素平分到各个桶中时的表现最好。
      // 如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会更好。
      function bucketSort(array, bucketSize = 5) {
        if (array.length < 2) {
          return array;
        }
        // 创建桶并将元素分布到不同的桶中
        const buckets = createBuckets(array, bucketSize);
        // 对每个桶执行插入排序算法和将所有桶合并为排序后的结果数组
        return sortBuckets(buckets);
      }

      // 创建桶
      function createBuckets(array, bucketSize) {
        let minValue = array[0];
        let maxValue = array[0];
        for (let i = 1; i < array.length; i++) {
          if (array[i] < minValue) {
            minValue = array[i];
          } else if (array[i] > maxValue) {
            maxValue = array[i];
          }
        }
        // 计算每个桶中需要分布的元素个数
        // 计算方法是：计算数组最大值和最小值的差值并与桶的大小进行除法计算
        const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
        const buckets = [];
        for (let i = 0; i < bucketCount; i++) {
          buckets[i] = [];
        }
        // 遍历数组中的每个元素，计算要将元素放到哪个桶中，并将元素插入正确的桶中
        for (let i = 0; i < array.length; i++) {
          const bucketIndex = Math.floor((array[i] - minValue) / bucketSize); 
          buckets[bucketIndex].push(array[i]);
        }
        return buckets;
      }

      // 将每个桶进行排序
      function sortBuckets(buckets) {
        const sortedArray = [];
        for (let i = 0; i < buckets.length; i++) {
          if (buckets[i] != null) {
            // 遍历每个可迭代的桶并应用插入排序，根据场景，我们还可以应用其他的排序算法，例如快速排序
            insertSort(buckets[i]);
            sortedArray.push(...buckets[i]);
          }
        }
        return sortedArray;
      }
      
      // 插入排序
      function insertSort(arr) {
        for (let i = 1; i < arr.length; i++) {
          const value = arr[i];
          let j = 0; // 插入的位置
          for (j = i - 1; j >= 0 && arr[j] > value; j--) {
            arr[j + 1] = arr[j]; // 移动数据
          }
          arr[j + 1] = value; // 插入数据
        }
      }

      const arr = [10, 6, 3, 4, 8, 1, 2];
      console.log(bucketSort(arr));
    </script>
  </body>
</html>
